class maxheap{
private:
	int heapsize;
public:
	void adjust_down(vector<int> &nums,int i){ //平衡子节点 
		int l=2*i+1,r=2*i+2,large=i;
		
		if(l<heapsize&&nums[l]>nums[large]) large=l;
		if(r<heapsize&&nums[r]>nums[large]) large=r; //找到该节点和两个子节点的最大值
		
		if(large!=i){
			swap(nums[i],nums[large]);
			adjust_down(nums,large);
		}
	}
	
	void adjust_up(vector<int> &nums,int i){ //平衡父节点
		int root=(i-1)/2;
		
		if(root>=0){
			if(nums[i]>nums[root]){
				swap(nums[i],nums[root]);
			}
			
			adjust_up(nums,root);
		}
	}
	
	void make_heap(vector<int> &nums){
		for(int i=heapsize/2-1;i>=0;i--){ //建堆 i一定要等于heapsize/2-1
			adjust_down(nums,i);
		}
	}
	
	void pop_heap(vector<int> &nums){ //弹出栈顶 将栈顶放到堆末尾并重新更新堆
		swap(nums[0],nums[heapsize-1]);
		heapsize--;
		adjust_down(nums,0);
	}
	
	void push_heap(vector<int> &nums){ //将需要添加的新元素添加到堆尾
		adjust_up(nums,heapsize);
		heapsize++;
	}
	
	heap(vector<int> &nums){
		heapsize=nums.size();

		make_heap(nums);
	}
};